package com.study.lu;

public class 最小花费爬楼梯 {
    /**
     * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
     * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
     * 请你计算并返回达到楼梯顶部的最低花费。
     * <p>
     * 示例一.
     * 输入：cost = [10,15,20]
     * 输出：15
     * 解释：你将从下标为 1 的台阶开始。
     * - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
     * 总花费为 15
     * <p>
     * 示例二.
     * 输入：cost = [1,100,1,1,1,100,1,1,100,1]
     * 输出：6
     * 解释：你将从下标为 0 的台阶开始。
     * - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
     * - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
     * - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
     * - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
     * - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
     * - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
     * 总花费为 6 。
     * <p>
     *
     * @param args
     */
    public static void main(String[] args) {
        //int[] cost = new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1};

        int[] cost = new int[]{10, 15, 20, 2};
        int i = bf(cost);
        /**
         * 题解
         * 求第n级台阶最小花费有两种解
         * 1.当到了n-1的时候，直接爬两个台阶即到顶部。minCost[n-2]+cost[i-1].
         * 2.当到了n的时候，直接爬过一个台阶即到顶部。应该是拿到minCost[n-1]+cost[i].
         * 则最小花费为 minCost[n] = min(minCost[n-2]+cost[i-1],minCost[n-1]+cost[i]).
         * 台阶的数组从0开始计数。可以用-1代表地面，并设cost[-1] = 0。
         * 最小总花费的初始值为：
         * 第0级台阶： minCost[0] = min(cost[-1], cost[0]) = min(0, cost[0]) = 0，
         * 第1级台阶： minCost[1] = min(cost[0], cost[1])。
         * 第N级台阶: minCost[n] = min(minCost[n-2]+cost[i-1],minCost[n-1]+cost[i]).
         */
        System.out.println(i);
    }

    private static int bf(int[] cost) {
        int[] minCost = new int[cost.length];
        minCost[0]=0;
        minCost[1] = Math.min(cost[0], cost[1]);
        for (int i = 2; i < cost.length; i++) {
            minCost[i] = Math.min(minCost[i-2]+cost[i-1],minCost[i-1]+cost[i]);
        }

        return minCost[cost.length-1];

    }


}
